﻿// CINTA作业14（3).cpp : 
/*/*
* File: CRT
* Author: Dongcheng Li
* Date: 201911119
* Purpose: to solve CRT:
* https://w.ketangpai.com/pages/homework/homework-detail.html
*/
#include<iostream>
using namespace std;
/*
* Input: an integer a,an integer b
* Output: return the result of CRT.
* Purpose: another way to the result of CRT.
* Method: According to the known knowledge of Egcd.
*/


int EGCD(int parameter_a, int parameter_b)//改成返回a的逆元
{
	int  space;
	int Counter = 1;//奇偶计数器

	int Determinant_a[3] = { 1,0, };
	int Determinant_b[3] = { 0,1, };
	if (parameter_a > parameter_b)
	{
		Determinant_a[2] = parameter_a;
		Determinant_b[2] = parameter_b;
	}
	else
	{
		Determinant_b[2] = parameter_a;
		Determinant_a[2] = parameter_b;
	}
	while (Determinant_a[2] % Determinant_b[2] != 0 || Determinant_b[2] % Determinant_a[2] != 0)
	{
		if (Counter % 2)
		{
			space = Determinant_a[2] / Determinant_b[2];
			Determinant_a[0] = Determinant_a[0] - (space * Determinant_b[0]);
			Determinant_a[1] = Determinant_a[1] - (space * Determinant_b[1]);
			Determinant_a[2] = Determinant_a[2] - (space * Determinant_b[2]);
		}
		else
		{
			space = Determinant_b[2] / Determinant_a[2];
			Determinant_b[0] = Determinant_b[0] - (space * Determinant_a[0]);
			Determinant_b[1] = Determinant_b[1] - (space * Determinant_a[1]);
			Determinant_b[2] = Determinant_b[2] - (space * Determinant_a[2]);
		}
		Counter++;
		if (Determinant_b[2] == 0 || Determinant_a[2] == 0)
		{
			break;
		}
	}
	if (Determinant_b[2] == 0)
	{
		if (parameter_a > parameter_b)
		{
			//cout << "r:" << Determinant_a[0] << " " << "s:" << Determinant_a[1] << " " << "d:" << Determinant_a[2] << endl;
			return Determinant_a[0];//r
		}
		else
		{
			//cout << "s:" << Determinant_a[0] << " " << "r:" << Determinant_a[1] << " " << "d:" << Determinant_a[2] << endl;
			return Determinant_a[1];//r
		}
	}
	if (Determinant_a[2] == 0)
	{
		if (parameter_a > parameter_b)
		{
			//cout << "r:" << Determinant_b[0] << " " << "s:" << Determinant_b[1] << " " << "d:" << Determinant_b[2] << endl;
			return Determinant_b[0];//r
		}
		else
		{
			//cout << "s:" << Determinant_b[0] << " " << "r:" << Determinant_b[1] << " " << "d:" << Determinant_b[2] << endl;
			return Determinant_b[1];//r
		}
	}

	
}

int main()
{/*
	int n, y;
	int M = 1;
	int x = 0;
	int abb = 0;
	cout << "方程个数n" << endl;
	cin >> n;
	int* m = new int[n];
	int* a = new int[n];


	cout << "依次输入a" << endl;
	for (int i = 0; i < n; i++)
	{

		cin >> a[i];

	}
	cout << "依次输入m" << endl;
	for (int i = 0; i < n; i++)
	{

		cin >> m[i];

	}

	for (int i = 0; i < n; i++)
	{

		M = M * m[i];
	}

	for (int i = 0; i < n; i++)
	{
		abb = a[i] * (M / m[i]) * EGCD(M / m[i], m[i]) + abb;
	}
	y = (abb % M + M) % M;//保证是正数


	cout << "result:" << y << endl;

	*/
	int n, y;
	int M = 1;
	int x = 0;
	int abb = 0;
	n = 2;
	int* m = new int[n];
	int* a = new int[n];
	m[0] = 5;
	m[1] = 7;
	int p[4]={ 1,2,3,4 };
	int q[6] = { 1,2,3,4 ,5,6};
	int j, k;
	for (k = 0; k < 4; k++)
	{
		for (j = 0; j < 6; j++)
		{
			M = 1;
			x = 0;
			abb = 0;
			a[0] = p[k];
			a[1] = q[j];


			for (int i = 0; i < n; i++)
			{

				M = M * m[i];
			}

			for (int i = 0; i < n; i++)
			{
				abb = a[i] * (M / m[i]) * EGCD(M / m[i], m[i]) + abb;
			}
			y = (abb % M + M) % M;//保证是正数


			cout << "result:" << y <<"<->("<< a[0]<<","<< a[1]<< ")"<<endl;
		}
	}
}